【题解】 [NOI2011]Noi嘉年华 决策单调性优化DP luoguP1973 | Qiuly's blog!

【题解】 [NOI2011]Noi嘉年华 决策单调性优化DP luoguP1973

Posted on | Edited on | In | Comments:

这道题一共有两问，第一问瞎搞 $\texttt{DP}$ ，第二问如果直接 $\texttt{DP}$ 的话复杂度是 $O(n^4)$ 的过不去，这个时候需要用到决策单调性优化复杂度就可以降低至 $O(n^3)$ ，这样就过了。我们先来讨论一下第一问的做法。

时间的范围太大了，我们需要离散化一下。离散化后时间就控制在 $0$ 到 $2n$ 的范围内了。

首先可以发现最终的答案一定就是一段一段时间，每一段时间内的活动都是在同一个会场举行。我们可以预处理一个 $tot_{l,r}$ 表示完全在时间 $l,r$ 之内的活动有多少个。计算直接暴力，预处理的复杂度为 $O(n^3)$ 。

然后设一个 $pre_{i,j}​$ 表示 $1​$ 到 $i​$ 的时间一个会场的活动数为 $j​$ 时另一个会场的最大活动数。那么转移的话我们枚举一个时间 $k​$ ，然后考虑 $k​$ 到 $i​$ 这段时间中的所有活动分配给哪个会场即可。可以得到转移方程：

这里我们 $pre$ 方程的定义中”一个会场”就是一号会场，”另一个会场”就是二号会场$。pre_{k,j}+tot_{k,i}$ 就是将 $k$ 到 $i$ 这段时间中所有活动都分配给了二号会场，$pre_{k,j-tot_{k,i}}$ 很显然就是分配给了一号会场。计算时枚举 $i,j,k$ ，复杂度是 $O(n^3)$ 。(其实准确的复杂度带个常数，因为 $i$ 枚举的是时间，而时间最大是 $2n$ 的) 。

我们设离散化后时间总长为 $m$ ，那么答案显然为 $\max\limits_{i=1}^m\{\min(pre_{m,i},i)\}$ 。接下来我们解决第二问。

我们的 $tot_{l,r}$ 统计的就是完全在时间 $l,r$ 的区间有多少个。那么对于第 $i$ 个活动，设该活动的起始时间与终止时间分别为 $s_i,t_i$ ，那么我们再考虑一对 $x,y \ \ (x\leq s_i,t_i\leq y)$ ，那么如果我们将答案计算上 $tot_{x,y}$ ，那么也就选择了第 $i$ 个活动了。

我们设 $f_{i,j}$ 表示一号会场强制选择 $i$ 到 $j$ 时间中的所有活动时的最优答案。(注意这里的最优答案就是两个会场中活动少的一方的最大值，我们只是考虑在一号会场强制选择 $i$ 到 $j​$ 中的所有活动的情况下考虑最优的全局答案) 。

继续看向一号会场，假设在 $i$ 前面的时间中一号会场已经合法举办了 $x$ 场活动，在 $j$ 后面的时间中也合法举办了 $y$ 场活动。那么我们枚举 $i,j,x,y$ 也可以得到二号会场的活动数：$i$ 前面的时间种有 $pre_{i,x}$ 场活动，$j$ 后面的时间中有……诶这里用 $pre$ 貌似不是很好表示诶，于是我们新定义一个 $suf$ ，$suf_{i,j}$ 表示 $i$ 到 $m$ 的时间一个会场的活动数为 $j$ 时另一个会场的最大活动数，$suf$ 的状态转移方程和 $pre$ 的同理。

枚举 $i,j,x,y$ 后就可以得到两个会场的活动个数，那么就可以直接算答案了：

但是这样子的复杂度是 $O(n^4)​$ 的，过不了。

不过，我们会发现，对于单调递增的 $x$ ，对应的最优的 $y$ 一定是单调递减的 。为什么呢？首先对于一个单调递增的 $i$ ，$pre_{?_i},suf_{?_i}$ 一定是单调递减的( $?$ 为任意数) 。那么如果对于单调递增的 $x$ ，$pre_{i,x}$ 一定是单调递减的，这个时候如果 $y$ 单调递增也就意味着 $suf_{j,y}$ 会单调递减，那么 $x+tot_{i,j}+y$ 和 $pre_{i,x}+suf_{j,y}$ 将会越拉越大，对于答案显然是不利的。反过来，如果 $y$ 是单调递减的，那么就会相对比较均衡。(感性理解理解……)

那么我们就不需要枚举 $y$ 了，只需要扫一扫就好了，最终计算 $f$ 的时间复杂度为 $O(n^3)$ 。

最终统计答案的时候，对于一个活动 $i$ ，我们的答案显然为 $\max\limits_{x=1}^{s_i}\max\limits_{y=t_i}^{m}f_{x,y}$ 。必须满足 $x\leq s_i,t_i\leq y$ ，因为这样就会满足一定会选择第 $i$ 个活动。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define F(i,j,k) for((i)=(j);(i)<=(k);++i)
#define R(i,j,k) for((i)=(j);(i)>=(k);--i)

const int N=4e2+9;
const int inf=1e9+9;

int n,m,i,j,k,l,r,s[N],t[N],b[N];
int tot[N][N],pre[N][N],suf[N][N],f[N][N];

inline int IN() {
    char ch;bool flag=0;int x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;return x;
}

inline int calc(int x,int y) 
{return min(x+tot[l][r]+y,pre[l][x]+suf[r][y]);}   

int main() {
    n=IN();
    F(i,1,n) b[++m]=s[i]=IN(),b[++m]=t[i]=IN()+s[i];
    sort(b+1,b+1+m),
    m=unique(b+1,b+1+m)-b-1;/*离散化去重*/
    F(i,1,n) {
        s[i]=lower_bound(b+1,b+1+m,s[i])-b;
        t[i]=lower_bound(b+1,b+1+m,t[i])-b;
        F(l,1,s[i]) R(r,m,t[i]) ++tot[l][r];/*计算出tot*/
    }
    F(i,1,m) F(j,1,n) pre[i][j]=suf[i][j]=-inf;/*初始化*/ 
    /*----------计算出pre和suf----------*/
    F(i,1,m) F(j,0,tot[1][i]) F(k,1,i) {
        pre[i][j]=max(pre[i][j],pre[k][j]+tot[k][i]);
        if(j>=tot[k][i]) pre[i][j]=max(pre[i][j],pre[k][j-tot[k][i]]);
    }
    R(i,m,1) F(j,0,tot[i][m]) F(k,i,m) {
        suf[i][j]=max(suf[i][j],suf[k][j]+tot[i][k]);
        if(j>=tot[i][k]) suf[i][j]=max(suf[i][j],suf[k][j-tot[i][k]]);
    }
    /*计算f*/
    F(l,1,m) F(r,l+1,m) for(int y=n,x=0;x<=n;++x) {/*y当做指针扫一遍*/
        int old_calc=calc(x,y),new_calc;
        while(y&&old_calc<=(new_calc=calc(x,y-1))) --y,old_calc=new_calc;
        f[l][r]=max(f[l][r],calc(x,y));/*转移*/
    }
    /*输出答案*/
    int ans=0;
    F(i,1,n) ans=max(ans,min(pre[m][i],i));
    printf("%d\n",ans);/*第一问*/
    F(i,1,n) {
        ans=0;
        F(l,1,s[i]) R(r,m,t[i]) ans=max(ans,f[l][r]);
        printf("%d\n",ans);/*第二问*/
    }return 0;
}

本文标题:【题解】 [NOI2011]Noi嘉年华 决策单调性优化DP luoguP1973

文章作者:Qiuly

发布时间:2019年04月22日 - 00:00

最后更新:2019年04月23日 - 08:42

原始链接:http://qiulyblog.github.io/2019/04/22/[题解]luoguP1973/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。